﻿#define _CRT_SECURE_NO_WARNINGS 1

//位图
//namespace bit
//{
//	// N是需要多少⽐特位
//	template<size_t N>
//	class bitset
//	{
//	public:
//		bitset()
//		{
//			//_bits.resize(N/32+1, 0);
//			_bits.resize((N >> 5) + 1, 0);
//		}
//
//		// 把x映射的位标记成1
//		void set(size_t x)
//		{
//			size_t i = x / 32;
//			size_t j = x % 32;
//			_bits[i] |= (1 << j);
//		}
//
//		// 把x映射的位标记成0
//		void reset(size_t x)
//		{
//			size_t i = x / 32;
//			size_t j = x % 32;
//			_bits[i] &= ~(1 << j);
//		}
//		bool test(size_t x)
//		{
//			size_t i = x / 32;
//			size_t j = x % 32;
//			return _bits[i] & (1 << j);
//		}
//	private:
//		vector<int> _bits;
//	};
//}
//int main()
//{
//	bit::bitset<100> bs1;
//	bs1.set(50);
//	bs1.set(30);
//	bs1.set(90);
//	for (size_t i = 0; i < 100; i++)
//	{
//		if (bs1.test(i))
//		{
//			cout << i << "->" << "在" << endl;
//		}
//		else
//		{
//			cout << i << "->" << "不在" << endl;
//		}
//	}
//	bs1.reset(90);
//	bs1.set(91);
//	cout << endl << endl;
//	for (size_t i = 0; i < 100; i++)
//	{
//		if (bs1.test(i))
//		{
//			cout << i << "->" << "在" << endl;
//		}
//		else
//		{
//			cout << i << "->" << "不在" << endl;
//		}
//	}
//
//	// 开2^32个位的位图
//	//bit::bitset<-1> bs2;
//	//bit::bitset<UINT_MAX> bs3;
//	//bit::bitset<0xffffffff> bs4;
//	return 0;
//}



// 模拟位图找交集
//void test_bitset1()
//{
//	int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };
//	int a2[] = { 5,3,5,99,6,99,33,66 };
//	bitset<100> bs1;
//	bitset<100> bs2;
//	for (auto e : a1)
//	{
//		bs1.set(e);
//	}
//	for (auto e : a2)
//	{
//		bs2.set(e);
//	}
//	for (size_t i = 0; i < 100; i++)
//	{
//		if (bs1.test(i) && bs2.test(i))
//		{
//			cout << i << endl;
//		}
//	}
//}
//
//template<size_t N>
//class twobitset
//{
//public:
//	void set(size_t x)
//	{
//		bool bit1 = _bs1.test(x);
//		bool bit2 = _bs2.test(x);
//		if (!bit1 && !bit2) // 00->01
//		{
//			_bs2.set(x);
//		}
//		else if (!bit1 && bit2) // 01->10
//		{
//			_bs1.set(x);
//			_bs2.reset(x);
//		}
//		else if (bit1 && !bit2) // 10->11
//		{
//			_bs1.set(x);
//			_bs2.set(x);
//		}
//	}
//	// 返回0 出现0次数
//	// 返回1 出现1次数
//	// 返回2 出现2次数
//	// 返回3 出现2次及以上
//	int get_count(size_t x)
//	{
//		bool bit1 = _bs1.test(x);
//		bool bit2 = _bs2.test(x);
//		if (!bit1 && !bit2)
//		{
//			return 0;
//		}
//		else if (!bit1 && bit2)
//		{
//			return 1;
//		}
//		else if (bit1 && !bit2)
//		{
//			return 2;
//		}
//		else
//		{
//			return 3;
//		}
//	}
//private:
//	bitset<N> _bs1;
//	bitset<N> _bs2;
//};
//};
//void test_bitset2()
//{
//	bit::twobitset<100> tbs;
//	int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };
//	for (auto e : a)
//	{
//		tbs.set(e);
//	}
//	for (size_t i = 0; i < 100; ++i)
//	{
//		//cout << i << "->" << tbs.get_count(i) << endl;
//		if (tbs.get_count(i) == 1 || tbs.get_count(i) == 2)
//		{
//			cout << i << endl;
//		}
//	}
//}


//布隆过滤器

//struct HashFuncBKDR
//{
//	/// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The C 
//	Programming Language》
//		// ⼀书被展⽰⽽得 名，是⼀种简单快捷的hash算法，也是Java⽬前采⽤的字符串的Hash
//		算法累乘因⼦为31。
//		size_t operator()(const string& s)
//	{
//		size_t hash = 0;
//		for (auto ch : s)
//		{
//			hash *= 31;
//			hash += ch;
//		}
//		return hash;
//	}
//};
//struct HashFuncAP
//{
//	// 由Arash Partow发明的⼀种hash算法。 
//	size_t operator()(const string& s)
//	{
//		size_t hash = 0;
//		for (size_t i = 0; i < s.size(); i++)
//		{
//			if ((i & 1) == 0) // 偶数位字符
//			{
//				hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
//			}
//			else // 奇数位字符
//			{
//				hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >>
//					5)));
//			}
//		}
//		return hash;
//	}
//};
//struct HashFuncDJB
//{
//	// 由Daniel J. Bernstein教授发明的⼀种hash算法。 
//	size_t operator()(const string& s)
//	{
//		size_t hash = 5381;
//		for (auto ch : s)
//		{
//			hash = hash * 33 ^ ch;
//		}
//		return hash;
//	}
//};
//template<size_t N,
//	size_t X = 6,
//	class K = string,
//	class Hash1 = HashFuncBKDR,
//	class Hash2 = HashFuncAP,
//	class Hash3 = HashFuncDJB>
//class BloomFilter
//{
//public:
//	void Set(const K& key)
//	{
//		size_t hash1 = Hash1()(key) % M;
//		size_t hash2 = Hash2()(key) % M;
//		size_t hash3 = Hash3()(key) % M;
//		_bs.set(hash1);
//		_bs.set(hash2);
//		_bs.set(hash3);
//	}
//	bool Test(const K& key)
//	{
//		size_t hash1 = Hash1()(key) % M;
//		if (_bs.test(hash1) == false)
//			return false;
//		size_t hash2 = Hash2()(key) % M;
//		if (_bs.test(hash2) == false)
//			return false;
//		size_t hash3 = Hash3()(key) % M;
//		if (_bs.test(hash3) == false)
//			return false;
//		return true; // 存在误判(有可能3个位都是跟别⼈冲突的，所以误判)
//	}
//
//	// 获取公式计算出的误判率
//	double getFalseProbability()
//	{
//		double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);
//		return p;
//	}
//private:
//	static const size_t M = X * N;
//	// 我们实现位图是⽤vector，也就是堆上开的空间
//	bit::bitset<M> _bs;
//	//std::bitset<M> _bs;
//	// vs下std的位图是开的静态数组，M太⼤会存在崩的问题
//	// 解决⽅案就是bitset对象整体new⼀下，空间就开到堆上了
//	//std::bitset<M>* _bs = new std::bitset<M>;
//};
//void TestBloomFilter1()
//{
//	string strs[] = { "百度","字节","腾讯" };
//	BloomFilter<10> bf;
//	for (auto& s : strs)
//	{
//		bf.Set(s);
//	}
//	for (auto& s : strs)
//	{
//		cout << bf.Test(s) << endl;
//	}
//	for (auto& s : strs)
//	{
//		cout << bf.Test(s + 'a') << endl;
//	}
//	cout << bf.Test("摆渡") << endl;
//	cout << bf.Test("百渡") << endl;
//}
//void TestBloomFilter2()
//{
//	srand(time(0));
//	const size_t N = 10000000;
//	BloomFilter<N> bf;
//	//BloomFilter<N, 3> bf;
//	//BloomFilter<N, 10> bf;
//	std::vector<std::string> v1;
//	std::string url = "https://www.cnblogs.com/-
//		clq / archive / 2012 / 05 / 31 / 2528153.html";
//		//std::string url = "https://www.baidu.com/s?ie=utf8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=ln2&fenlei=256&rsv_pq=0x8d9962
//		630072789f & rsv_t = ceda1rulSdBxDLjBdX4484KaopD % 2BzBFgV1uZn4271RV0PonRFJm0i5xAJ % 2F
//		Do & rqlang = en & rsv_enter = 1 & rsv_dl = ib & rsv_sug3 = 3 & rsv_sug1 = 2 & rsv_sug7 = 100 & rsv_sug2 =
//		0 & rsv_btype = i & inputT = 330 & rsv_sug4 = 2535";
//
//		//std::string url = "猪⼋戒";
//		for (size_t i = 0; i < N; ++i)
//		{
//			v1.push_back(url + std::to_string(i));
//		}
//	for (auto& str : v1)
//	{
//		bf.Set(str);
//	}
//	// v2跟v1是相似字符串集（前缀⼀样），但是后缀不⼀样
//	v1.clear();
//	for (size_t i = 0; i < N; ++i)
//	{
//		std::string urlstr = url;
//		urlstr += std::to_string(9999999 + i);
//		v1.push_back(urlstr);
//	}
//	size_t n2 = 0;
//	for (auto& str : v1)
//	{
//		if (bf.Test(str)) // 误判
//		{
//			++n2;
//		}
//	}
//	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
//	// 不相似字符串集 前缀后缀都不⼀样
//	v1.clear();
//	for (size_t i = 0; i < N; ++i)
//	{
//		//string url = "zhihu.com";
//		string url = "孙悟空";
//		url += std::to_string(i + rand());
//		v1.push_back(url);
//	}
//	size_t n3 = 0;
//	for (auto& str : v1)
//	{
//		if (bf.Test(str))
//		{
//			++n3;
//		}
//	}
//	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
//
//	cout << "公式计算出的误判率:" << bf.getFalseProbability() << endl;
//}
//int main()
//{
//	TestBloomFilter2();
//	return 0;
//}


